package com.algorithm.sort;

import java.util.Arrays;

/**
 * @program: 归并排序
 * @author: luhd
 * @create: 2021-08-10
 */
public class MergeSort {
    public static void main(String[] args) {
        /**
         * 归并排序是建立在归并操作上的一种有效的排序算法。
         * 该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
         * 将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。
         * 若将两个有序表合并成一个有序表，称为2-路归并。
         */
        int [] arr = {15,5,3,7,9 ,2,18,10,20,6};
        MergeSort(arr);
        /**
         *   归并排序结果：
         *      5 15
         *      7 9
         *      3 7 9
         *      3 5 7 9 15
         *      2 18
         *      6 20
         *      6 10 20
         *      2 6 10 18 20
         *      2 3 5 6 7 9 10 15 18 20
         */
    }

    /**
     *
     * @param arr   分治算法的核心，分而治之，将大问题化解成若干个小问题----->得到的是若干个小的已经排序的数组，逐步合并成大的数组
     * @return  无限细分的数组，如{15,5,3,7,9 ,2,18,10,20,6}，{15,5,3,7,9},{15,3},{3,7,9},{3},{7,9},{7,9}
     */
    public static int[] MergeSort(int[] arr){
        if(arr.length < 2) return arr;
        int mid = arr.length / 2;
        int[] left = Arrays.copyOfRange(arr,0,mid);  //不包含数组下标为mid的
        int[] right = Arrays.copyOfRange(arr,mid,arr.length);  //不包含数组下标为arr.length的
        return Merge(MergeSort(left),MergeSort(right));    //将已经分好的左右数组，继续无限细分，且夹杂着有序数组的合并(Merge)方法
    }

    /**
     *  归并排序：将两段已经排序好的数组合并成一个有序数组，，当左子（右子）序列只有一个值时，可以认为是有序的
     * @param left  左子序列（有序）
     * @param right  右子序列（有序）
     * @return
     */
    public static int[] Merge(int[] left, int[] right){
        int[] result = new int[left.length + right.length];
        for(int index = 0, i = 0, j = 0; index < result.length ; index++){
            if(i >= left.length){       //两个有序数组，当左子序列的指针(举个例子，指针)，指向左子序列的最后一位，即只需要排右子序列即可，因为有序直接插入
                result[index] = right[j++];
            }else if(j >= right.length){    //同上，即右子序列提前插入完，已经全部在结果数组中，此时只需要关注左子序列即可
                result[index] = left[i++];
            }else if(left[i] > right[j]){   //核心逻辑，在两个左右数组均未排完的情况下，挨个比较左右数组的值的大小
                result[index] = right[j++]; //j++   先赋值再自增，顺次比较
            }else{
                result[index] = left[i++];
            }
        }
        for (int i = 0; i < result.length; i++) {
            System.out.print(result[i]+" ");
        }
        System.out.println();
        return result;
    }
}
